package leetcode.D700.T695;

class Solution {
    // 一刷
    /*private static final int[] dx = {0, 0, -1, 1};
    private static final int[] dy = {-1, 1, 0, 0};
    private boolean[][] isv;
    private int maxArea = 0;
    public int maxAreaOfIsland(int[][] grid) {
        if(grid.length == 0) {
            return 0;
        }
        int m = grid.length, n = grid[0].length;
        isv = new boolean[m][n];
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                if(grid[i][j] == 0 || isv[i][j]) {
                    continue;
                }
                maxArea = Math.max(dfs(grid, i, j), maxArea);
            }
        }
        return maxArea;
    }
    private int dfs(int[][] grid, int x, int y) {
        int area = 1;

        isv[x][y] = true;
        for(int i=0; i<4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(isValid(nx, ny, grid)) {
                int temp = dfs(grid, nx, ny);
                area += temp;
            }
        }
        return area;
    }
    private boolean isValid(int x, int y, int[][] grid) {
        int m = grid.length, n = grid[0].length;
        if(x < 0 || x >= m || y < 0 || y >= n) {
            return false;
        }
        if(isv[x][y] || grid[x][y] == 0) {
            return false;
        }
        return true;
    }*/

    // 二刷
    private static final int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length, maxArea = 0;
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                maxArea = Math.max(maxArea, dfs(grid, i, j));
            }
        }
        return maxArea;
    }
    private int dfs(int[][] grid, int row, int col) {
        if (grid[row][col] == 0)
            return 0;
        grid[row][col] = 0;
        int m = grid.length, n = grid[0].length, area=1;
        for (int[] dir : dirs) {
            int x = row+dir[0], y = col+dir[1];
            if(x>=0 && x<m && y>=0 && y<n)
                area += dfs(grid, x, y);
        }
        return area;
    }
}